2509. The post office
For preparation to the final phase of Russian Code Cup the organizers need
to send to the contest place n items.
The weight of each item is known and equals in grams to mi.
It was decided to send the items using the service “Superexpress”. The
service takes forwarding parcels, each may send one or more items. The weight
of each parcel equals to the total weight of items in it.
Sending parcels costs 1 ruble per gram, except for parcels that are
subject to the special offer. Namely, if the parcel weighs exactly one
kilogram, the cost of its shipping is p
rubles.
The organizers of Russian Code Cup want to send all the items, spending
the minimum amount of money. Help them to distribute the items to the parcels
to achieve this.
Input. The first line contains two integers: n and p (1 ≤ n ≤ 14; 1 ≤ p ≤ 1000) – the number of items
and the delivery cost of a parcel using special offer. The second line contains
n integers m1, m2,
..., mn (1 ≤ mi ≤ 1000 for all i from 1 to n).
Output. Print the minimum total
cost of delivery of all items in rubles.
|
Sample
input |
Sample
output |
5 800
100 200 300
400 500 |
1300 |
SOLUTION
dynamic
programming – the masks
Algorithm analysis
Введем понятие маски, описывающую подмножество пересылаемых
предметов. Например, mask = 5 = 1012
соответствует подмножеству, которое включает в себя нулевой и второй предметы
(предметы будем нумеровать с нуля).
Для каждого
подмножества предметов вычислим их суммарный вес, равный стоимости пересылки.
Если он в точности равен 1000, то из того что p ≤ 1000, всегда следует воспользоваться специальным
предложением.
Пусть MinCost[mask] содержит
минимальную стоимость в рублях пересылки подмножества предметов, описываемых
маской mask. Тогда для
любого подмножества x, являющегося
подмножеством mask, имеет место соотношение
MinCost[mask] = 
Поскольку маска 2n
– 1 соответствует всему множеству из n
элементов, то ответом задачи будет значение MinCost[2n – 1].
Теорема. Перебор всех масок, а для них
подмасок выполняется за O(3n).
Доказательство 1. Рассмотрим i-ый бит. Для него имеется три варианта:
·
он входит в маску mask и подмаску sub;
·
он входит в маску mask но не входит в подмаску sub;
·
он не входит ни в маску mask, ни в подмаску sub;
Всего битов n, поэтому различных комбинаций 3n.
Доказательство 2. Пусть маска mask имеет k включенных битов. Тогда она будет иметь 2k подмасок. Количество масок длины n с k включенными битами
равно 
. Следовательно число комбинаций равно
= (1 + 2)n = 3n
Algorithm realization
Массы предметов
будем хранить в массиве m. В ячейке MinCost[mask] будем хранить минимальную стоимость в
рублях пересылки подмножества предметов, описываемых маской mask.
int m[15], MinCost[1 << 14];
Читаем входные
данные.
scanf("%d %d",&n,&p);
for(i = 0; i < n; i++) scanf("%d",&m[i]);
В переменной mask перебираем все возможные маски от 0 до 2n – 1.
for(mask = 0; mask < (1 << n);
mask++)
{
В переменную Cost занесем вес подмножества предметов, соответствующих маске mask. Просматриваем двоичный код числа mask. Если на его i-ой позиции находится 1, то включаем в Cost вес i-го предмета.
for(Cost
= i = 0; i < n; i++)
if (mask
& (1 << i)) Cost += m[i];
Если значение Cost строго равно 1000, то из того что p ≤ 1000
(дано по условию), следует присвоить переменной Cost значение p.
if (Cost
== 1000) Cost = p;
Занесем найденную стоимость пересылки
в соответствующую ячейку массива MinCost.
MinCost[mask] = Cost;
}
Для каждой маски mask перебираем все подмножества x Ì mask (x будет подмножеством mask
тогда и только тогда, когда mask AND x равно x). Если из множества, которому соответствует маска mask, вычесть множество соответствующее x, то получится множество с маской mask XOR x. Например, если mask =
11012, x = 10012
, то mask XOR x = 1002. Что соответствует теоретико - множественной
операции {1, 3, 4} \ {1, 4} = {3}.
for(mask = 0; mask < (1 << n);
mask++)
for(x = 0; x
< mask; x++)
Пересчитываем значение MinCost[mask] согласно приведенному в анализе
задачи рекуррентному соотношению.
if ((mask & x) == x)
MinCost[mask] = min(MinCost[mask],MinCost[mask^x] + MinCost[x]);
Выводим ответ, который находится в ячейке MinCost[2n – 1].
printf("%d\n",MinCost[(1
<< n) - 1]);
Реализация с оценкой O(3n)
#include <stdio.h>
#include <string.h>
#define MAX 0xFFFFFFFF
int n, p, Cost, i, mask, x;
unsigned int
m[15], MinCost[1 << 14];
unsigned int
min(unsigned int
i, unsigned int
j)
{
return (i
< j) ? i : j;
}
Для маски mask следует перебрать все подмаски sub, вычислим минимум среди всех возможных сумм FindCost(sub) + FindCost(mask ^ sub). Ввиду
симметрии суммы достаточно перебирать только те подмаски sub, для которых sub
≥ mask ^ sub.
unsigned int
FindCost(int mask)
{
if
(MinCost[mask] != MAX) return MinCost[mask];
// sub перебирает
все подмаски маски mask
for (int sub = (mask - 1) & mask;
sub >= mask ^ sub; sub = (sub -
1) & mask)
MinCost[mask] =
min(MinCost[mask], FindCost(sub) + FindCost(mask ^ sub));
return
MinCost[mask];
}
int main(void)
{
Установим MinCost[mask] = -1, если стоимость отправки набора предметов, которые задаются
подмножеством mask, еще не вычислена.
memset(MinCost,0xFF,sizeof(MinCost));
Читаем входные данные.
scanf("%d
%d",&n,&p);
for(i = 0; i
< n; i++) scanf("%d",&m[i]);
Если стоимость некоторого
подмножества предметов не больше 1000 (именно не больше, а не меньше так как
возможен случай p = 1000), то специальное
предложение для их отправки не может быть использовано. Для таких подмножеств
сразу можно вычислить MinCost[mask] как сумму стоимостей всех предметов. Если сумма стоимостей
предметов равна в точности 1000, то положим MinCost[mask] = p.
for(mask = 0;
mask < (1 << n); mask++)
{
for(Cost =
i = 0; i < n; i++)
if (mask
& (1 << i)) Cost += m[i];
if (Cost ==
1000) Cost = p;
if (Cost
<= 1000) MinCost[mask] = Cost;
}
Выводим ответ. Все множество
предметов задается маской 2n
– 1, двоичное представление которой состоит из n единиц.
printf("%u\n",FindCost((1
<< n) - 1));
return 0;
}